package NO1_Array;

/**
 * 2025-08-25
 * 力扣 - 55. 跳跃游戏
 * <p>
 * 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
 */
public class CanJumpMain {
    public static void main(String[] args) {
        System.out.println(canJump(new int[]{2, 3, 1, 1, 4}));
    }

    // 倒序遍历，只要某一个位置满足到达终点，就只需考虑前面的是否能够到达该位置即可
//    public static boolean canJump(int[] nums) {
//        if (nums.length == 1){
//            return true;
//        }
//        int lastPos = nums.length - 1;
//        for (int i = lastPos; i >= 0; i--){
//            if (i + nums[i] >= lastPos){
//                // 可以跳到该位置，重新赋值判断前面的位置是否可以到达该位置
//                lastPos = i;
//            }
//        }
//        return lastPos == 0;
//    }

    // 贪心
    public static boolean canJump(int[] nums) {
        int maxReach = 0; // 当前能到达的最远位置
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            // 如果当前位置已经超过了能到达的最远位置，说明无法到达
            if (i > maxReach) {
                return false;
            }

            // 更新能到达的最远位置
            maxReach = Math.max(maxReach, i + nums[i]);

            // 如果已经能到达终点，提前返回
            if (maxReach >= n - 1) {
                return true;
            }
        }

        return maxReach >= n - 1;
    }
}
